package main.Q801_900;

import java.util.*;

public class Q811_820 {
    public static void main(String[] args) {
        System.out.println("Question811：子域名访问计数");
        System.out.println("Question812：");
        System.out.println("Question813：");
        System.out.println("Question814：二叉树剪枝");
        System.out.println("Question815：公交路线");
        System.out.println("Question816：");
        System.out.println("Question817：");
        System.out.println("Question818：");
        System.out.println("Question819：");
        System.out.println("Question820：单词的压缩编码");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Question811 {
    public List<String> subdomainVisits(String[] cpdomains) {
        Map<String, Integer> map = new HashMap<>();
        List<String> result = new ArrayList<>();
        for (String s : cpdomains) {
            String[] sub = s.split(" ");
            int count = Integer.parseInt(sub[0]);// 最低级域名的数量
            int len = sub[1].length();
            for (int i = len - 1; i >= 0; i--) {// 倒序处理子域名
                if (sub[1].charAt(i) == '.') {
                    map.put(sub[1].substring(i + 1, len), map.getOrDefault(sub[1].substring(i + 1, len), 0) + count);
                }
            }
            map.put(sub[1].substring(0, len), map.getOrDefault(sub[1].substring(0, len), 0) + count);//  最低级域名前面没有 '.'，单独处理
        }
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            result.add(entry.getValue() + " " + entry.getKey());
        }
        return result;
    }
}

class Question814 {
    public boolean process(TreeNode root) {
        if (root == null) return true;//空节点
        boolean left = process(root.left), right = process(root.right);//左右子树情况
        if (left && right && root.val == 0) {//左右子树为空，本节点为0
            return true;
        } else {
            if (left) root.left = null;
            if (right) root.right = null;
            return false;
        }

    }

    public TreeNode pruneTree(TreeNode root) {
        boolean left = process(root.left), right = process(root.right);
        if (left) root.left = null;
        if (right) root.right = null;
        if (left && right && root.val == 0) root = null;
        return root;
    }
}

class Question815 {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        int length = routes.length;
        boolean[][] edges = new boolean[length][length];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < length; i++) {//建立邻接矩阵
            for (int station : routes[i]) {
                List<Integer> list = map.getOrDefault(station, new ArrayList<>());
                for (int j : list) {
                    edges[i][j] = true;
                    edges[j][i] = true;
                }
                list.add(i);
                map.put(station, list);
            }
        }
        int[] dis = new int[length];
        Arrays.fill(dis, -1);
        Queue<Integer> queue = new LinkedList<>();
        for (int bus : map.getOrDefault(source, new ArrayList<>())) {
            dis[bus] = 1;
            queue.offer(bus);
        }
        while (!queue.isEmpty()) {
            int x = queue.poll();
            for (int y = 0; y < length; y++) {
                if (edges[x][y] && dis[y] == -1) {
                    dis[y] = dis[x] + 1;
                    queue.offer(y);
                }
            }
        }
        int ret = Integer.MAX_VALUE;
        for (int bus : map.getOrDefault(target, new ArrayList<Integer>())) {
            if (dis[bus] != -1) {
                ret = Math.min(ret, dis[bus]);
            }
        }
        return ret == Integer.MAX_VALUE ? -1 : ret;
    }
}

class Question820 {
    public int minimumLengthEncoding(String[] words) {
        Set<String> good = new HashSet<String>(Arrays.asList(words));
        for (String word : words) {
            for (int k = 1; k < word.length(); ++k) {
                good.remove(word.substring(k));
            }
        }

        int ans = 0;
        for (String word : good) {
            ans += word.length() + 1;
        }
        return ans;
    }
}